Many people now are using mobile devices with various methods of connectivity as the primary gateway to the Internet and also as major storage points for personal information. This is in addition to the normal range of personal computers, associated sensors, and Internet-based providers of information. Combining these devices together, in addition to the applications on the devices and the information stored by those applications, is a major challenge of interoperability. This can be achieved through numerous, individual and personal distributed spaces of information and computations in which persons, groups of persons, etc. can place, share, interact and manipulate (or program devices to automatically perform the planning, interaction and manipulation of) webs of distributed information and/or computations with their own locally agreed semantics without necessarily conforming to an unobtainable, global whole.
On the other hand, in order to improve manageability, performance and availability of the information, these distributed information spaces are built based on large-scale distributed data storages (e.g., databases) that can scale to petabytes or even larger with the capability of maintaining ordered access keys. However, the existing architectures for distributed database management, such as, for example, Google BigTable®, Cassandra®, HBase®, etc. require centralized management of key ranges. Although the central key management approaches are capable of distributed key rebalancing, however the key rebalancing processes of these approaches are localized by each server. As a result, the key management process may create system bottlenecks that in turn will limit system scalability, performance and availability, as a centralized process creates a single point of failure.